#pragma once
#include<vector>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<fstream>
#include<sstream>
#include<algorithm>
using namespace std;
namespace ID3
{
	class Node
	{
	public:
		int attrIndex;	//属性索引方便后续的查询
		string attributeValue;		//属性值
		string label;	//该节点的标签
		bool isLeaf;	//是否为叶结点
		vector<Node*> children;	//子女节点
		//map<string, vector<string>> dataset;		//记录数据集

		Node()
			:isLeaf(false)
		{  }

	};

	//数据表
	class DataSet
	{
	public:
		vector<string> attribute;		//属性集合
		vector<vector<string>> data;		//数据集合
		map< string, vector<string>> table;		//属性+数据集合

		void ConnectAttributeValue() {		//将属性与数据列进行关联
			vector< vector<string>> attributeValueList;	//属性值列表
			vector<string> tempAttr = attribute;
			tempAttr.push_back("classList");		//添加一个类别列属性
			attributeValueList.resize(tempAttr.size());
			for (size_t i = 0; i < tempAttr.size(); i++)
			{
				for (size_t j = 0; j < data.size(); j++)
				{
					attributeValueList[i].push_back(data[j][i]);		//类似于将data进行转置
				}
				table.emplace(tempAttr[i], attributeValueList[i]);	//将转置过的一行数据值与相应属性像连接
			}
		}
		DataSet(const vector<vector<string>>& data, const vector<string>& attribute)
			:data(data), attribute(attribute) {
			ConnectAttributeValue();
		}
	};

	//决策树
	class DecisionTree
	{
	public:
		DecisionTree(const DataSet& dataSet)
			:dataSet(dataSet) {
			for (size_t i = 0; i < dataSet.attribute.size(); i++)
			{
				attrIndex.insert({ dataSet.attribute[i],i });
			}
			CreateTree(this->dataSet, &root);
		}

		void print() {
			levelPrint(root);
		}

		string Classify(const vector<string>& testVec) {
			return RecursionQuery(root, testVec);
		}

		~DecisionTree()
		{
			DestoryDecisionTree(root);
		}

	private:
		DataSet dataSet;		//数据集
		Node* root = nullptr;		//创建根节点
		map<string, int> attrIndex;		//记录属性的索引
		vector<pair<string,vector<double>>> Gini_values; //记录每次分类时每种属性的Gini值。
		vector<double> values; //记录每种属性的Gini值
		vector<double> I; //样本整体信息熵
		void CreateTree(DataSet& dataSet, Node** treeNode) {		//传递指针的地址**
			vector<string> classList = dataSet.table["classList"];  //类别列表
			set<string> classCount;
			for (size_t i = 0; i < classList.size(); i++)
			{
				classCount.insert(classList[i]);
			}
			if (classCount.size() == 1)		//判断是否所有成员都属同一类
			{
				(*treeNode) = new Node();	//实例化指针
				(*treeNode)->isLeaf = true;
				(*treeNode)->label = classList[0];
				return;
			}
			if (dataSet.attribute.empty() || dataSet.table.size() == 1)	//也就是集合内只有一列元素或者是属性集合为空
			{
				(*treeNode) = new Node();
				(*treeNode)->isLeaf = true;
				(*treeNode)->label = majorityCnt(classList);   //返回类型出现最多的类别标签
				return;
			}
			//int kkkk = 10;
			int bestFeat = chooseBestFeatureToSplit(dataSet);//--正常版本
			//int bestFeat = chooseBestFeatureToSplit_avg(dataSet);//--平均值版本
			/*if (bestFeat == -1)
				return;*/
			string bestFeatLabel = dataSet.attribute[bestFeat];
			Gini_values.push_back({ bestFeatLabel,values });
			values = {};
			(*treeNode) = new Node();
			(*treeNode)->label = bestFeatLabel;
			(*treeNode)->attrIndex = attrIndex[bestFeatLabel];
			vector<string> featValue = dataSet.table[bestFeatLabel];	//获取所有最优属性的属性值
			set<string> uniqueVal;
			for (size_t i = 0; i < featValue.size(); i++)
			{   
				uniqueVal.insert(featValue[i]);
			}
			for (auto item : uniqueVal)
			{
				Node* node = nullptr;	//创建一个节点
				auto tam = splitDataSet(dataSet, bestFeat, item);
				CreateTree(tam, &node);
				node->attributeValue = item;	//赋给其属性值
				(*treeNode)->children.push_back(node);		//将创建好的节点与父节点相连接
			}
		}

		//为了筛选出出现次数最多的类别(yes or no)
		string majorityCnt(const vector<string>& classList) {
			string majorLabel = "";
			map<string, int> value;

			for (size_t i = 0; i < classList.size(); i++)
			{
				if (!value.count(classList[i]))
				{
					value.insert({ classList[i],0 });
				}
				value[classList[i]]++;
			}

			int tempCount = 0;
			for (auto item = value.begin(); item != value.end(); item++)
			{
				if (item->second > tempCount)
				{
					tempCount = item->second;
					majorLabel = item->first;
				}
			}

			return majorLabel;
		}

		//挑选出数据表中最优的属性
		int chooseBestFeatureToSplit_avg(DataSet& dataSet) //模块平均值版本
		{
			int numFeat = dataSet.table.size() - 1;	//属性的数量
			double baseEntropy = calcShannonEnt(dataSet);
			I.push_back(baseEntropy);
			double bestGain = -0.1;		//记录信息增益
			int bestFeature = -1;		//记录最优属性的索引值
			int f1=0; //第一模块
			int index_f1 = -1;
			double most_f1=-0.1;
			double sum_f1=0.0;
			int f2=0;//第二模块
			int index_f2 =-1;
			double sum_f2=0.0;
			double most_f2=-0.1;
			int f3=0;//第三模块
			int index_f3 = -1;
			double sum_f3=0.0;
			double most_f3=-0.1;

			for (size_t i = 0; i < numFeat; i++)
			{
				//获取dataSet中的第i列所有属性值
				string feat = dataSet.attribute[i];
				vector<string> featList = dataSet.table[feat];	//获取相应属性的数据集
				set<string> uniqueVal;
				for (size_t i = 0; i < featList.size(); i++)
				{
					uniqueVal.insert(featList[i]);
				}

				double newEntropy = 0.0;
				for (auto item = uniqueVal.begin(); item != uniqueVal.end(); item++)
				{
					DataSet subDataSet = splitDataSet(dataSet, i, *item);		//按照属性值(0 or 1)来划分属性
					double prob = subDataSet.data.size() / (double)dataSet.data.size();
					newEntropy += prob * calcShannonEnt(subDataSet);
				}
				double infoGain = baseEntropy - newEntropy;
				//cout << "信息增益：" << infoGain<<endl;
				if (feat == "robot_rember_most_reaction" || feat == "robot_rember_bias")
				{
					f1++;
					sum_f1 += infoGain;
					if (infoGain > most_f1)
					{
						most_f1 = infoGain;
						index_f1 = i;
					}
				}
				else if (feat == "people_short_rember_count" || feat == "people_short_rember_reaction" || feat == "people_short_rember_bias" || feat == "people_short_rember_most_reaction" || feat == "people_short_rember_time_gap")
				{
					f2++;
					sum_f2 += infoGain;
					if (infoGain > most_f2)
					{
						most_f2 = infoGain;
						index_f2 = i;
					}
				}
				else if (feat == "long_rember_bias" || feat == "long_rember_reaction")
				{
					f3++;
					sum_f3 += infoGain;
					if (infoGain > most_f3)
					{
						most_f3 = infoGain;
						index_f3 = i;
					}
				}
				else
				{
					if (infoGain > bestGain)
					{
						bestGain = infoGain;
						bestFeature = i;
					}
				}
				values.push_back(infoGain);
			}
			double avg_1 = -0.1;
			if (f1 != 0.0)
				avg_1 = sum_f1 / f1;
			double avg_2 = -0.1;
			if (f2 != 0.0)
				avg_2 = sum_f2 / f2;
			double avg_3 = -0.1;
			if (f3 != 0.0)
				avg_3 = sum_f3 / f3;
			double maxs = max(max(bestGain, avg_1), max(avg_2, avg_3));
			if (maxs == bestGain)
				return bestFeature;
			else if (maxs == avg_1)
				return index_f1;
			else if (maxs == avg_2)
				return index_f2;
			else
				return index_f3;
		}

		int chooseBestFeatureToSplit(DataSet& dataSet) //正常版本
		{
			int numFeat = dataSet.table.size() - 1;	//属性的数量
			double baseEntropy = calcShannonEnt(dataSet);
			I.push_back(baseEntropy);
			double bestGain = -0.1;		//记录信息增益
			int bestFeature = -1;		//记录最优属性的索引值
			for (size_t i = 0; i < numFeat; i++)
			{
				//获取dataSet中的第i列所有属性值
				string feat = dataSet.attribute[i];
				vector<string> featList = dataSet.table[feat];	//获取相应属性的数据集
				set<string> uniqueVal;
				for (size_t i = 0; i < featList.size(); i++)
				{
					uniqueVal.insert(featList[i]);
				}

				double newEntropy = 0.0;
				for (auto item = uniqueVal.begin(); item != uniqueVal.end(); item++)
				{
					DataSet subDataSet = splitDataSet(dataSet, i, *item);		//按照属性值(0 or 1)来划分属性
					double prob = subDataSet.data.size() / (double)dataSet.data.size();
					newEntropy += prob * calcShannonEnt(subDataSet);
				}
				double infoGain = baseEntropy - newEntropy;
				//cout << "信息增益：" << infoGain<<endl;
			
				if (infoGain > bestGain)
				{
					bestGain = infoGain;
					bestFeature = i;
				}
				values.push_back(infoGain);
				
			}
			return bestFeature;
		}

		//计算香农熵
		double calcShannonEnt(DataSet& dataSet) {
			int numEntries = dataSet.data.size();		//获取数据集的行数
			map<string, int> labelCount;		//记录每个标签出现的次数
			vector<string> classList = dataSet.table["classList"];

			for (size_t i = 0; i < classList.size(); i++)
			{
				if (!labelCount.count(classList[i]))
				{
					labelCount.insert({ classList[i],0 });
				}
				labelCount[classList[i]]++;
			}

			double shannonEnt = 0.0;		//记录香农熵
			for (auto item = labelCount.begin(); item != labelCount.end(); item++)
			{
				double prob = (double)item->second / numEntries;	//计算该标签的概率
				shannonEnt -= prob * log(prob) / log(2);
			}
			return shannonEnt;
		}

		//划分数据集
		DataSet splitDataSet(const DataSet& dataSet, int index, string value) {
			vector<string> attr;
			for (size_t i = 0; i < dataSet.attribute.size(); i++)
			{
				if (index == i)
					continue;
				attr.push_back(dataSet.attribute[i]);		//记录属性信息
			}

			vector <vector<string>> data, oldData = dataSet.data;
			for (size_t i = 0; i < oldData.size(); i++)
			{

				if (oldData[i][index] != value)
					continue;
				vector<string> accessAttrVec;
				for (size_t j = 0; j < oldData[i].size(); j++)
				{
					if (index == j)
						continue;
					accessAttrVec.push_back(oldData[i][j]);		//记录要提取的数据信息
				}
				data.push_back(accessAttrVec);
			}

			return DataSet(data, attr);
		}

		//递归遍历
		void print(const Node* node) {
			if (!node->isLeaf)
			{
				for (size_t i = 0; i < node->children.size(); i++)
				{
					print(node->children[i]);
				}
			}
			cout << node->label << " " << node->attributeValue << endl;
		}

		//层次遍历
		void levelPrint(Node* node) {
			queue<Node*> queue;
			queue.push(node);
			while (!queue.empty())
			{
				Node* currentNode = queue.front();
				queue.pop();
				cout << currentNode->label << " " << currentNode->attributeValue << endl;
				if (!currentNode->isLeaf)
				{
					for (size_t i = 0; i < currentNode->children.size(); i++)
					{
						queue.push(currentNode->children[i]);
					}
				}
			}
		}

		//递归查询
		string RecursionQuery(const Node* node, const vector<string>& testVec) {
			if (node->isLeaf)
			{
				return node->label;
			}
			else
			{
				for (size_t i = 0; i < node->children.size(); i++)
				{
					Node* currentNode = node->children[i];
					if (currentNode->attributeValue == testVec[node->attrIndex])
					{
						return RecursionQuery(node->children[i], testVec);
					}
				}
			}
		}

		//释放内存
		void DestoryDecisionTree(Node* node) {
			if (!node->isLeaf)
			{
				for (size_t i = 0; i < node->children.size(); i++)
				{
					DestoryDecisionTree(node->children[i]);
				}
			}
			delete node;	//释放节点
			node = nullptr;
		}
	};

	//io读取数据
	vector<vector<string>> ReadTrainData(string file_name)
	{
		ifstream infile(file_name.c_str());
		vector<vector<string>> datas;
		string line;
		while (getline(infile, line))
		{
			vector<string> data;
			string words;
			istringstream iss(line);
			while (iss >> words)
			{
				data.push_back(words);
			}
			datas.push_back(data);
		}
		infile.close();
		return datas;
	}

	vector<pair<vector<string>, string>> ReadTestData(string file_name)
	{
		ifstream infile(file_name.c_str());
		vector<pair<vector<string>,string>> datas;
		string line;

		while (getline(infile, line))
		{
			vector<string> data;
			string result;
			string words;
			istringstream iss(line);
			int i = 1;
			while (iss >> words)
			{
				if (i == 12)
				{
					result = words;
				}
				else
					data.push_back(words);
				i++;
			}
			datas.push_back(make_pair(data,result));
		}
		return datas;
	}
	bool String_one(string& s1, string& s2)
	{
		int pos1 = s1.find('+');
		int pos2 = s2.find('+');
		string s1_1 = s1.substr(0, pos1);
		string s2_1 = s2.substr(0, pos2);
		string s1_2 = s1.substr(pos1 + 1);
		string s2_2 = s2.substr(pos2 + 1);
		if (s1_1 == s2_1 || s1_2 == s2_2)
			return true;
		else
			return false;
	}
	double TestingAccuracy(vector<pair<vector<string>, string>>& datas, DecisionTree& tree)
	{
		fstream file;
		file.open("result--prediction--Normal--前向预测-2-27-2.txt", ios::app);
		//file.open("result--prediction--Avg--前向预测-2-27-2.txt", ios::app);
		double a = 0;
		string pre = "站立+正常";
		for (int i = 0; i < datas.size(); i++)
		{
			string result = tree.Classify(datas[i].first);
			/*if (result .empty())
				result = "站立+正常";*/
			if (result.empty())
			{
				result = pre;
			}
			else
				pre = result;
			if (result == datas[i].second || String_one(result, datas[i].second))
			{
				a++;
			}
			else
			{
				file << i+1<<"  " << "真实：" << datas[i].second << "  " <<"预测：" << result << endl;
			}
		}
		file.close();
		double res = (a / datas.size())*100;
		return res;
	}
}
